Search for: All records

Abstract In group testing, the goal is to identify a subset of defective items within a larger set of items based on tests whose outcomes indicate whether at least one defective item is present. This problem is relevant in areas such as medical testing, DNA sequencing, communication protocols and many more. In this paper, we study (i) a sparsity-constrained version of the problem, in which the testing procedure is subjected to one of the following two constraints: items are finitely divisible and thus may participate in at most $$\gamma $$ tests; or tests are size-constrained to pool no more than $$\rho $$ items per test; and (ii) a noisy version of the problem, where each test outcome is independently flipped with some constant probability. Under each of these settings, considering the for-each recovery guarantee with asymptotically vanishing error probability, we introduce a fast splitting algorithm and establish its near-optimality not only in terms of the number of tests, but also in terms of the decoding time. While the most basic formulations of our algorithms require $$\varOmega (n)$$ storage for each algorithm, we also provide low-storage variants based on hashing, with similar recovery guarantees. 

Abstract In this paper, we consider the problem of noiseless non-adaptive probabilistic group testing, in which the goal is high-probability recovery of the defective set. We show that in the case of $$n$$ items among which $$k$$ are defective, the smallest possible number of tests equals $$\min \{ C_{k,n} k \log n, n\}$$ up to lower-order asymptotic terms, where $$C_{k,n}$$ is a uniformly bounded constant (varying depending on the scaling of $$k$$ with respect to $$n$$) with a simple explicit expression. The algorithmic upper bound follows from a minor adaptation of an existing analysis of the Definite Defectives algorithm, and the algorithm-independent lower bound builds on existing works for the regimes $$k \le n^{1-\varOmega (1)}$$ and $$k = \varTheta (n)$$. In sufficiently sparse regimes (including $$k = o\big ( \frac{n}{\log n} \big )$$), our main result generalizes that of Coja-Oghlan et al. (2020) by avoiding the assumption $$k \le n^{1-\varOmega (1)}$$, whereas in sufficiently dense regimes (including $$k = \omega \big ( \frac{n}{\log n} \big )$$), our main result shows that individual testing is asymptotically optimal for any non-zero target success probability, thus strengthening an existing result of Aldridge (2019, IEEE Trans. Inf. Theory, 65, 2058–2061) in terms of both the error probability and the assumed scaling of $$k$$.